home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung / Power-Programmierung (Tewi)(1994).iso / magazine / pcmagazi / 1992 / 04 / sort.cpp < prev    next >
C/C++ Source or Header  |  1992-02-05  |  4KB  |  163 lines
  1. // sort.cpp RHS 7/29/91
  2.  
  3. #include "sort.h"
  4. /*-----------------------------------------------------------------------*
  5.  
  6. Name            Swap - exchanges two objects
  7.  
  8. Usage           void  near pascal  Swap (void  *left,
  9.                                                      void *right);
  10.  
  11. Description     exchanges the elWidth byte wide objects pointed to
  12.                 by left and right.
  13.  
  14. Return value    Nothing
  15.  
  16. *------------------------------------------------------------------------*/
  17.  
  18. void near pascal swap2(FARPPV left, FARPPV right)
  19.     {
  20.     asm     push Ds
  21.     asm     cld
  22.         // note that elWidth is never 0, since it's tested at entry to QSort
  23.     asm     mov Cx, 4
  24.     asm     les Di, right
  25.     asm     lds Si, left
  26.  
  27.     asm     shr Cx, 1               // test for an odd number of bytes
  28.     asm     jnc xch_wordLoop
  29.  
  30.     asm     mov Al, Es:[Di]
  31.     asm     movsb                   // swap bytes, advancing pointers
  32.     asm     mov [Si-1], Al
  33.     asm     jz  xch_end             // if CX was originally 1      
  34.  
  35. xch_wordLoop:
  36.     asm     mov Ax, Es:[Di]
  37.     asm     movsw                   // swap words, advancing pointers
  38.     asm     mov  [Si-2], Ax
  39.     asm     loop xch_wordLoop
  40.  
  41. xch_end:
  42.     asm     pop Ds
  43.     return;
  44.     }
  45.  
  46. void near pascal Sort::Swap(void FAR *left, void FAR *right)
  47.     {
  48.     int i;
  49.     unsigned char c;
  50.  
  51.     for(i = 0; i < elWidth; i++)
  52.         {
  53.         c = *((unsigned char far *)right);
  54.         *((unsigned char *)right)++ = *((unsigned char far *)left);
  55.         *((unsigned char far *)left)++ = c;
  56.         }
  57.     return;
  58.     }
  59.  
  60. /*
  61.   Optimize pointer comparisons knowing segments are identical,
  62.   except in HUGE model.
  63. */
  64.  
  65.  
  66. /*-----------------------------------------------------------------------*
  67.  
  68. Name            QSort - performs the quicker sort
  69.  
  70. Usage           void  near pascal  QSort (char *base,
  71.                                                      size_t numEl);
  72.  
  73. Description     performs the quicker sort on the numEl element array
  74.                 pointed to by base.
  75.  
  76. Return value    Nothing
  77.  
  78. *------------------------------------------------------------------------*/
  79. #pragma warn -sig
  80. void near pascal Sort::QSort(char FAR *base, size_t numEl)
  81.     {
  82.     char FAR *left, FAR *right;
  83.     unsigned lNum;
  84.  
  85. TailRecursionOpt:
  86.     if(numEl < 2)
  87.         {
  88.         if(numEl == 2)
  89.             if(PCmpFunc(base, right = elWidth + base) > 0)
  90.                 swap2((FARPPV) base, (FARPPV) right);
  91.         return;
  92.         }
  93.  
  94.     right = (numEl - 1) * elWidth + base;
  95.     left = (numEl >> 1) * elWidth + base;
  96.  
  97.         // sort the pivot, left, and right elements for "median of 3"
  98.  
  99.     if(PCmpFunc(left, right) > 0)
  100.         swap2((FARPPV) left, (FARPPV) right);
  101.  
  102.     if(PCmpFunc(left, base) > 0)
  103.         swap2((FARPPV) left, (FARPPV) base);
  104.  
  105.     else if(PCmpFunc(base, right) > 0)
  106.         swap2((FARPPV) base, (FARPPV) right);
  107.  
  108.  
  109.     if(numEl == 3)
  110.         {
  111.         swap2((FARPPV) base, (FARPPV) left);
  112.         return;
  113.         }
  114.  
  115.         // now for the classic Hoare algorithm
  116.  
  117.     left = elWidth + base;
  118.     do
  119.         {
  120.         while(PCmpFunc(left, base) < 0)
  121.             if(left < right)
  122.                 left += elWidth;
  123.             else
  124.                 goto Break;
  125.  
  126.         while(left < right)
  127.             if(PCmpFunc(base, right) <= 0)
  128.                 right -= elWidth;
  129.             else
  130.                 {
  131.                 swap2((FARPPV) left, (FARPPV) right);
  132.                 left += elWidth;
  133.                 right -= elWidth;
  134.                 break;
  135.                 }
  136.         }
  137.     while(left < right);
  138.  
  139. Break:
  140.     if(PCmpFunc(left, base) < 0)
  141.         swap2((FARPPV) left, (FARPPV) base);
  142.  
  143.  
  144.     lNum = (left - base) / elWidth;
  145.  
  146.     if(numEl -= lNum)
  147.         QSort(left, numEl);
  148.  
  149.     numEl = lNum;
  150.     goto TailRecursionOpt;
  151.     }
  152.  
  153. #pragma warn .sig
  154. void Sort::QuickSort(void FAR *base, size_t numEl, size_t width, CmpFunc *compar)
  155.     {
  156.     if((elWidth = width) == 0)
  157.         return;
  158.  
  159.     PCmpFunc = compar;
  160.  
  161.     QSort((char FAR *)base, numEl);
  162.     }
  163.